package top.hkyzf.study.leetcode.graph;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * description:
 *
 * @author zhufeng
 * @version 1.0
 * @date 2024-4-4 18:16
 */
public class 有向无环图中一个节点的所有祖先_2192 {
    /**
     * 方法一，正向建图
     * @param n 图节点数
     * @param edges 边
     * @return 返回结果
     */
    public List<List<Integer>> getAncestors1(int n, int[][] edges) {
        List<List<Integer>> ansList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ansList.add(new ArrayList<>());
        }
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
        }
        int[] visit = new int[n];
        for (int i = 0; i < n; i++) {
            visit[i] = -1;
        }

        for (int start = 0; start < n; start++) {
            dfs1(start, start, visit, graph, ansList);
        }
        return ansList;
    }

    private void dfs1(int start, int cur, int[] visit, List<Integer>[] graph, List<List<Integer>> ansList) {
        visit[cur] = start;
        List<Integer> g = graph[cur];
        for (int i : g) {
            if (visit[i] != start) {
                ansList.get(i).add(start);
                dfs1(start, i, visit, graph, ansList);
            }
        }
    }

    /**
     * 方法二，反向见图
     * @param n 图节点数
     * @param edges 边
     * @return 返回结果
     */
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> ansList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            ansList.add(new ArrayList<>());
        }
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[1]].add(edge[0]);
        }
        int[] visit = new int[n];
        for (int start = 0; start < n; start++) {
            for (int i = 0; i < n; i++) {
                visit[i] = -1;
            }
            dfs(start, visit, graph);
            visit[start] = -1;
            for (int i = 0; i < n; i++) {
                if (visit[i] == 1) {
                    ansList.get(start).add(i);
                }
            }
        }
        return ansList;
    }

    private void dfs(int start, int[] visit, List<Integer>[] graph) {
        visit[start] = 1;
        List<Integer> g = graph[start];
        for (int i : g) {
            if (visit[i] != 1) {
                dfs(i, visit, graph);
            }
        }
    }

    @Test
    public void testGetAncestors () {
        int n = 8;
        int[][] edges = {{0,3},{0,4},{1,3},{2,4},{2,7},{3,5},{3,6},{3,7},{4,6}};
        System.out.println(getAncestors(n, edges));
    }
}
